{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉搜索树中的中序后继"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: inorderSuccessor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树中的中序后继"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉搜索树和其中的一个节点 <code>p</code> ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 <code>null</code> 。</p>\n",
    "\n",
    "<p>节点&nbsp;<code>p</code>&nbsp;的后继是值比&nbsp;<code>p.val</code>&nbsp;大的节点中键值最小的节点，即按中序遍历的顺序节点 <code>p</code> 的下一个节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/23/285_example_1.PNG\" style=\"height: 117px; width: 122px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,3], p = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/23/285_example_2.PNG\" style=\"height: 229px; width: 246px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,3,6,2,4,null,null,1], p = 6\n",
    "<strong>输出：</strong>null\n",
    "<strong>解释：</strong>因为给出的节点没有中序后继，所以答案就返回 <code>null 了。</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 10<sup>4</sup>]</code> 内。</li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>树中各节点的值均保证唯一。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 285&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/inorder-successor-in-bst/\">https://leetcode-cn.com/problems/inorder-successor-in-bst/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [P5rCT8](https://leetcode.cn/problems/P5rCT8/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [P5rCT8](https://leetcode.cn/problems/P5rCT8/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        def issame(p1, p2):\n",
    "            if p1 is None and p2 is None:\n",
    "                return True\n",
    "            \n",
    "            if p1.val != p2.val:\n",
    "                return False\n",
    "            else:\n",
    "                return issame(p1.left, p2.left) and issame(p1.right, p2.right)\n",
    "\n",
    "        self.flag = False\n",
    "        self.res = None\n",
    "        def traverse(root):\n",
    "            if root is None:\n",
    "                return \n",
    "            traverse(root.left)\n",
    "            if self.flag:\n",
    "                self.res = root\n",
    "                self.flag = False\n",
    "            if issame(root, p):\n",
    "                self.flag = True\n",
    "            traverse(root.right)\n",
    "        traverse(root)\n",
    "        return self.res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ans = None\n",
    "        while root:\n",
    "            if root.val > p.val:\n",
    "                ans = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if not root:\n",
    "            return\n",
    "        # 如果当前节点值小于等于p，那么后继节点必然在右子树中\n",
    "        if root.val <= p.val:\n",
    "            return self.inorderSuccessor(root.right, p)\n",
    "        # 如果当前节点大于p，那么后继节点必然在当前节点或者左子树中\n",
    "        left = self.inorderSuccessor(root.left, p)\n",
    "        # 如果左子树搜索结果不为空，则返回左子树的搜索结果\n",
    "        if left:\n",
    "            return left\n",
    "        # 否则当前节点即为后继节点\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if not root: return None\n",
    "        self.res = None\n",
    "        def inorder(root):\n",
    "            if not root: return\n",
    "            inorder(root.left)\n",
    "            if not self.res and root.val > p.val:\n",
    "                self.res = root\n",
    "                return\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        return self.res\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        node = p.right\n",
    "        if node:\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "        \n",
    "        cur = root\n",
    "        res = None\n",
    "        while cur:\n",
    "            if cur.val <= p.val:\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                res = cur\n",
    "                cur = cur.left\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        self.res = []\n",
    "        self.tmp = None\n",
    "        self.inorder(root, p)\n",
    "        if self.tmp == len(self.res):\n",
    "            return None\n",
    "        return self.res[self.tmp]\n",
    "\n",
    "    def inorder(self,root,p):\n",
    "        if not root:\n",
    "            return \n",
    "        self.inorder(root.left,p)\n",
    "        self.res.append(root)\n",
    "        #存p的下一个index\n",
    "        if root == p:\n",
    "            self.tmp = len(self.res)\n",
    "        self.inorder(root.right, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        \n",
    "        successor = None\n",
    "        if p.right:\n",
    "            successor = p.right\n",
    "            while successor.left:\n",
    "                successor = successor.left\n",
    "            return successor\n",
    "        node = root\n",
    "        while node:\n",
    "            if node.val>p.val:\n",
    "                successor = node\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        return successor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        stack = [None, root]\n",
    "        visit = set()\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur == p:\n",
    "                if cur.right:\n",
    "                    nex = cur.right\n",
    "                    while nex.left: nex = nex.left\n",
    "                    return nex\n",
    "                else:\n",
    "                    return stack[-1]\n",
    "            if cur.val not in visit:\n",
    "                visit.add(cur.val)\n",
    "                if cur.right:   stack.append(cur.right)\n",
    "                stack.append(cur)\n",
    "                if cur.left:    stack.append(cur.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        stack = [None, root]\n",
    "        visit = set()\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur == p:\n",
    "                if cur.right:\n",
    "                    nex = cur.right\n",
    "                    while nex.left: nex = nex.left\n",
    "                    return nex\n",
    "                else:\n",
    "                    return stack[-1]\n",
    "            if cur.val not in visit:\n",
    "                visit.add(cur.val)\n",
    "                if cur.right:   stack.append(cur.right)\n",
    "                stack.append(cur)\n",
    "                if cur.left:    stack.append(cur.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        successor = None\n",
    "        node = root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                successor = node\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        return successor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        def _leftmost(node):\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "\n",
    "        if p.right:\n",
    "            # 如果有右子树\n",
    "            return _leftmost(p.right)\n",
    "        else:\n",
    "            # 如果没有右子树，利用二叉搜索树的性质从root节点往下找\n",
    "            node, post_node = root, None\n",
    "            while node and node != p:\n",
    "                if node.val > p.val:\n",
    "                    post_node = node\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    node = node.right\n",
    "            return post_node\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        cur = root\n",
    "        result = None\n",
    "        while cur:\n",
    "            if cur.val > p.val:\n",
    "                result = cur\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ans = None\n",
    "        while root != None:\n",
    "            if root.val > p.val:\n",
    "                ans = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: \"TreeNode\", p: \"TreeNode\") -> \"TreeNode\":\n",
    "        # 方法1: 中序+pre\n",
    "        res = None\n",
    "        pre = None\n",
    "\n",
    "        def inorder(node):\n",
    "            nonlocal res, pre\n",
    "            if not node:\n",
    "                return\n",
    "            inorder(node.left)\n",
    "            if pre == p:\n",
    "                res = node\n",
    "            pre = node\n",
    "            inorder(node.right)\n",
    "\n",
    "        inorder(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        self.res = None\n",
    "        self.find = False\n",
    "\n",
    "        def dfs(node, p):\n",
    "            if not node: return\n",
    "            if self.res: return\n",
    "\n",
    "            dfs(node.left, p)\n",
    "            if self.find:\n",
    "                self.res = node\n",
    "                self.find = False\n",
    "            elif node == p:\n",
    "                self.find = True\n",
    "            dfs(node.right, p)\n",
    "        \n",
    "        dfs(root, p)\n",
    "        return self.res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        cur = root\n",
    "        result = None\n",
    "        while cur:\n",
    "            if cur.val > p.val:\n",
    "                result = cur\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ans=None\n",
    "        while root:\n",
    "            if root.val>p.val:\n",
    "                ans=root\n",
    "                root=root.left\n",
    "            else:\n",
    "                root=root.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        stack = [(1,root)]\n",
    "        next_flag = False\n",
    "        while stack:\n",
    "            flag,node = stack.pop(-1)\n",
    "            if not node:continue\n",
    "            if flag==1:\n",
    "                stack.append((1,node.right))\n",
    "                stack.append((0,node))\n",
    "                if not node==p:\n",
    "                    stack.append((1,node.left))\n",
    "                # else:\n",
    "                #     stack.append((1,None))\n",
    "            else:\n",
    "                if next_flag:\n",
    "                    return node\n",
    "                if node==p:\n",
    "                    next_flag=True\n",
    "                \n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        # 比p节点值大的最小树节点值（二叉搜索树而非二叉树）\n",
    "        if root is None:\n",
    "            return root\n",
    "\n",
    "        if root.val <= p.val:\n",
    "            return self.inorderSuccessor(root.right, p)\n",
    "        left = self.inorderSuccessor(root.left, p)\n",
    "        if left:\n",
    "            return left\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        load = []\n",
    "        def dfs(root, load):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs(root.left, load)\n",
    "            load.append((root.val, root))\n",
    "            dfs(root.right, load)\n",
    "        dfs(root, load)\n",
    "        index = load.index((p.val, p))\n",
    "        for v in load[index+1:]:\n",
    "            if v[0] > p.val:\n",
    "                return v[1]\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        stack = [(1,root)]\n",
    "        next_flag = False\n",
    "        while stack:\n",
    "            flag,node = stack.pop(-1)\n",
    "            if not node:continue\n",
    "            if flag==1:\n",
    "                stack.append((1,node.right))\n",
    "                stack.append((0,node))\n",
    "                if not node==p:\n",
    "                    stack.append((1,node.left))\n",
    "                else:\n",
    "                    stack.append((1,None))\n",
    "            else:\n",
    "                if next_flag:\n",
    "                    return node\n",
    "                if node==p:\n",
    "                    next_flag=True\n",
    "                \n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    pre = None\n",
    "    ret = None\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        def check(node):\n",
    "            if not node: return\n",
    "            # 中序遍历（左、中、右）\n",
    "            check(node.left)\n",
    "            # 若当前节点的前置节点为p，则说明当前节点即为所求\n",
    "            if self.pre == p: self.ret = node\n",
    "            self.pre = node\n",
    "            check(node.right)\n",
    "        \n",
    "        check(root)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        pre = None\n",
    "        flag = False\n",
    "        res = None\n",
    "        def dfs(root):\n",
    "            if root is None: return \n",
    "            dfs(root.left)\n",
    "            nonlocal pre, flag\n",
    "            pre = root\n",
    "            if flag:\n",
    "                nonlocal res\n",
    "                res = root \n",
    "                flag = False\n",
    "                return \n",
    "            if root == p:\n",
    "                flag = True\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ans = None\n",
    "        while root:\n",
    "            if root.val>p.val:\n",
    "                ans = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        falg=False\n",
    "        def midbl(q):\n",
    "            print(q.val)\n",
    "            if q is None:\n",
    "                return None\n",
    "            if q.left:\n",
    "                t= midbl(q.left)\n",
    "                if t is not None:\n",
    "                    return t\n",
    "            if q.val==p.val:\n",
    "                nonlocal falg\n",
    "                falg=True\n",
    "            if falg==True  and q.val>p.val:\n",
    "                return q\n",
    "            if q.right:\n",
    "                t=midbl(q.right)\n",
    "                if t is not None:\n",
    "                    return t\n",
    "            return None\n",
    "        # ans=None\n",
    "        return  midbl(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        res = None\n",
    "        findp = False\n",
    "        def inorder(node):\n",
    "            nonlocal res, findp\n",
    "            if not node:\n",
    "                return\n",
    "            inorder(node.left)\n",
    "            if findp and res is None:\n",
    "                res = node\n",
    "            if node == p:\n",
    "                findp = True\n",
    "            inorder(node.right)\n",
    "        inorder(root)\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ans = None\n",
    "\n",
    "        while root != None:\n",
    "            if root.val > p.val:\n",
    "                ans = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        stack = []\n",
    "        cur = root\n",
    "        pre = None\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop(-1)\n",
    "                if pre == p:\n",
    "                    return cur\n",
    "                pre = cur\n",
    "                cur = cur.right\n",
    "        return None\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root,q) :\n",
    "        \n",
    "        minmax=None\n",
    "        ptr=root\n",
    "        while ptr!=None:\n",
    "            if ptr.val>q.val:\n",
    "                minmax=ptr\n",
    "                ptr=ptr.left\n",
    "            else:\n",
    "                ptr=ptr.right\n",
    "        return minmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        inorder = list()\n",
    "        mapping = dict()\n",
    "        stack = list()\n",
    "        cur = root\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            top = stack.pop()\n",
    "            inorder.append(top)\n",
    "            mapping[top] = len(inorder) - 1\n",
    "            cur = top.right\n",
    "        index = mapping[p]\n",
    "        if index == len(inorder) - 1:\n",
    "            return None\n",
    "        return inorder[index + 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        self.hit = False \n",
    "        self.ans = None \n",
    "        self.dfs(root, p)\n",
    "        if self.ans:\n",
    "            return self.ans \n",
    "        return None\n",
    "\n",
    "    def dfs(self, root, p):\n",
    "\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        self.dfs(root.left, p)\n",
    "        \n",
    "        if self.hit == True:\n",
    "            if self.ans is None:\n",
    "                self.ans = root \n",
    "            return  \n",
    "\n",
    "        if p.val == root.val:\n",
    "            self.hit = True \n",
    "\n",
    "        self.dfs(root.right, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':    \n",
    "        successor = None\n",
    "        node = root\n",
    "        while node:\n",
    "            if node.val > p.val:\n",
    "                successor = node\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        return successor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if not root:\n",
    "            return None\n",
    "        cur,res = root,None\n",
    "        while cur:\n",
    "            if cur.val>p.val:\n",
    "                res = cur\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        self.is_find = False\n",
    "        self.result = None\n",
    "\n",
    "        self.dfs(root, p)\n",
    "\n",
    "        return self.result\n",
    "    \n",
    "    def dfs(self,node,p,):\n",
    "\n",
    "        if node.left:\n",
    "            self.dfs(node.left, p)\n",
    "\n",
    "        if self.is_find:\n",
    "            self.result = node\n",
    "            self.is_find = False\n",
    "            return\n",
    "\n",
    "        if node.val == p.val:\n",
    "            self.is_find = True\n",
    "\n",
    "        if node.right:\n",
    "            self.dfs(node.right, p)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if root == None or p == None:\n",
    "            return None\n",
    "        stack = []\n",
    "        # res = []\n",
    "        preVal = None\n",
    "        while len(stack) > 0 or root:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                # res.append(root.val)\n",
    "                if preVal == p.val:\n",
    "                    return root\n",
    "                preVal = root.val\n",
    "                root = root.right\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        res = []\n",
    "        num = []\n",
    "        flag = False\n",
    "        def dfs(root):\n",
    "            nonlocal res,num,p,flag\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if root == p:\n",
    "                flag = True\n",
    "            if flag == True and root.val>p.val:\n",
    "                res.append(root)\n",
    "                num.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        if not res:\n",
    "            return None\n",
    "        else:\n",
    "            pilot = num[0]\n",
    "            ret = res[0]\n",
    "            for i,n in enumerate(num):\n",
    "                if n < pilot:\n",
    "                    ret = res[i]\n",
    "            return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "\n",
    "        if p.right:\n",
    "            p = p.right\n",
    "            while p.left:\n",
    "                p = p.left\n",
    "            return p\n",
    "        else:\n",
    "            tmp_ans = None\n",
    "            while root:\n",
    "                if root.val > p.val:\n",
    "                    tmp_ans = root # 记录由根至p，遇到的最小的一个大于p的值\n",
    "                    root = root.left\n",
    "                else:\n",
    "                    root = root.right\n",
    "            return tmp_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        self.res=TreeNode(100001)\n",
    "        self.search(root, p)\n",
    "        if self.res.val==100001:\n",
    "            return None\n",
    "        else:\n",
    "            return self.res\n",
    "\n",
    "    def search(self, node, p):\n",
    "        if not node:\n",
    "            return\n",
    "        self.search(node.left, p)\n",
    "        if node.val>p.val:\n",
    "            if node.val<self.res.val:\n",
    "                self.res=node\n",
    "        self.search(node.right, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     pre = None\n",
    "#     ret = None\n",
    "#     def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "#         def check(node):\n",
    "#             if not node: return\n",
    "#             # 中序遍历（左、中、右）\n",
    "#             check(node.left)\n",
    "#             # 若当前节点的前置节点为p，则说明当前节点即为所求\n",
    "#             if self.pre == p: self.ret = node\n",
    "#             self.pre = node\n",
    "#             check(node.right)\n",
    "        \n",
    "#         check(root)\n",
    "#         return self.ret\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ans = None\n",
    "        if not root: return None\n",
    "        \n",
    "        while root:\n",
    "            # 如果当前节点的值大于或等于节点p的值，那么当前节点有可能是p的下一个节点，此时当前节点的值比节点p的值大，\n",
    "            # 但节点p的下一个节点是所有比它大的节点中值最小的一个，因此接下来前往当前节点的左子树，确定是否能找到值更小，但仍然大于节点p的值的节点\n",
    "            if root.val > p.val:\n",
    "                ans = root\n",
    "                root = root.left\n",
    "            # 根据二叉搜素树的中序遍历性质，目标节点p的下一个节点的值一定不会比p的值小，所以如果碰到比p的值小的节点说明需要向当前节点的右子树前进（即应该朝着更大的方向搜索）\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "        self.res = None\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if not root:\n",
    "            return None\n",
    "        self.mid_travel(root, p)\n",
    "        return  self.res\n",
    "\n",
    "    \n",
    "    def mid_travel(self, root, p):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.mid_travel(root.left, p)\n",
    "        if not self.res and root.val > p.val:\n",
    "            self.res = root\n",
    "            return \n",
    "        self.mid_travel(root.right, p)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        res = None\n",
    "\n",
    "        while root:\n",
    "            if root.val > p.val:\n",
    "                res = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if not root: return None\n",
    "        if root.val <= p.val: # p在root的右子树上面\n",
    "            return self.inorderSuccessor(root.right, p)\n",
    "        ans = self.inorderSuccessor(root.left, p)\n",
    "        return root if not ans else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: \"TreeNode\", p: \"TreeNode\") -> \"TreeNode\":\n",
    "        # 方法2: 二分查找\n",
    "        cur = root\n",
    "        res = None\n",
    "        while cur:\n",
    "            if cur.val > p.val:\n",
    "                if res is None or cur.val < res.val:\n",
    "                    # 当前节点是第一个大于p的, 或者它小于res, 更新它为最终结果\n",
    "                    res = cur\n",
    "                # 向右子树方向继续查找\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                # 向左子树方向继续查找\n",
    "                cur = cur.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ans = None\n",
    "        pt = False\n",
    "        def zz(node: TreeNode):\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal ans, pt\n",
    "            zz(node.left)\n",
    "            if pt and ans is None:\n",
    "                ans = node\n",
    "            elif not pt and node == p:\n",
    "                pt = True\n",
    "            zz(node.right)\n",
    "\n",
    "        zz(root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: \"TreeNode\", p: \"TreeNode\") -> \"TreeNode\":\n",
    "        # 方法1: 中序+pre\n",
    "        res = None\n",
    "        pre = None\n",
    "\n",
    "        def inorder(cur):\n",
    "            nonlocal res, pre\n",
    "            if not cur:\n",
    "                return\n",
    "            inorder(cur.left)\n",
    "            if pre == p:\n",
    "                # pre是p, 自然cur就是p的中序后继\n",
    "                res = cur\n",
    "            # 更新pre为当前节点, 用于下个节点的判断\n",
    "            pre = cur\n",
    "            inorder(cur.right)\n",
    "\n",
    "        inorder(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ms = []\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            ms.append(root)\n",
    "            inorder(root.right)\n",
    "\n",
    "        inorder(root)\n",
    "\n",
    "        for i in range(len(ms)):\n",
    "            if ms[i].val==p.val:\n",
    "                if i<len(ms)-1:\n",
    "                    return ms[i+1]\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if not root: return None\n",
    "        stack = []\n",
    "        flag = False\n",
    "        tmp = root\n",
    "        while stack or tmp:\n",
    "            while tmp:\n",
    "                stack.append(tmp)\n",
    "                tmp = tmp.left\n",
    "            tmp = stack.pop()\n",
    "            if flag:\n",
    "                return tmp\n",
    "            if tmp == p:\n",
    "                flag = True\n",
    "            tmp = tmp.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        res = None\n",
    "        while root != None:\n",
    "            if root.val <= p.val:\n",
    "                root = root.right\n",
    "            else:\n",
    "                res = root\n",
    "                root = root.left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        stack = []\n",
    "        cur = root\n",
    "        pre = None\n",
    "        while cur or len(stack) > 0:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            if pre and pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        \n",
    "        return None\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        ans = None\n",
    "        enable = 0\n",
    "        def mid(node):\n",
    "            nonlocal ans, enable\n",
    "            if not node:\n",
    "                return\n",
    "            mid(node.left)\n",
    "            if enable == 2:\n",
    "                return\n",
    "            elif enable == 1:\n",
    "                ans = node\n",
    "                enable = 2\n",
    "            elif node.val == p.val:\n",
    "                enable = 1\n",
    "            mid(node.right)\n",
    "        mid(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            nodes.append(node)\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "\n",
    "        nodes = []\n",
    "        dfs(root)\n",
    "\n",
    "        if p.val == nodes[-1].val:\n",
    "            return None\n",
    "        for i in range(len(nodes)-1):\n",
    "            if p.val == nodes[i].val:\n",
    "                return nodes[i+1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if p.right:\n",
    "            node = p.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            return node\n",
    "\n",
    "        ret = None\n",
    "        while root:\n",
    "            if root.val > p.val:\n",
    "                ret = root\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if p.right:\n",
    "            res = p.right\n",
    "            while res.left:\n",
    "                res = res.left\n",
    "                pass\n",
    "            return res\n",
    "        res = None\n",
    "        while root:\n",
    "            if root.val > p.val:\n",
    "                res = root\n",
    "                root = root.left\n",
    "                pass\n",
    "            else:\n",
    "                root = root.right\n",
    "                pass\n",
    "            pass\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        queue,ans,cur=[],None,root\n",
    "\n",
    "        while queue or cur:\n",
    "            while cur:\n",
    "                queue.append(cur)\n",
    "                cur=cur.left\n",
    "            cur=queue.pop()\n",
    "            if ans==p:\n",
    "                return cur\n",
    "            ans=cur\n",
    "            cur=cur.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        method = 'mine2'\n",
    "        if method == 'mine':\n",
    "            #中序遍历\n",
    "            res = []\n",
    "            def dfs(root):\n",
    "                if not root: return\n",
    "                dfs(root.left)\n",
    "                res.append(root)\n",
    "                dfs(root.right)\n",
    "            \n",
    "            dfs(root)\n",
    "            n = len(res)\n",
    "            for i in range(n):\n",
    "                if res[i] == p:\n",
    "                    if i == n - 1:\n",
    "                        return \n",
    "                    return res[i + 1]\n",
    "\n",
    "        if method == 'mine2':\n",
    "            res = None\n",
    "            if p.right:\n",
    "                res = p.right\n",
    "                while res.left:\n",
    "                    res = res.left\n",
    "                return res\n",
    "            node = root\n",
    "            while node:\n",
    "                if node.val > p.val:\n",
    "                    res = node\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    node = node.right\n",
    "            return res\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        path = []\n",
    "        while root:\n",
    "            path.append(root)\n",
    "            if root.val > p.val:\n",
    "                root = root.left\n",
    "                pass\n",
    "            elif root.val < p.val:\n",
    "                root = root.right\n",
    "                pass\n",
    "            else:\n",
    "                break\n",
    "                pass\n",
    "            pass\n",
    "        if root.right:\n",
    "            res = root.right\n",
    "            while res.left:\n",
    "                res = res.left\n",
    "                pass\n",
    "            return res\n",
    "        else:\n",
    "            for i in range(len(path) - 1, -1, -1):\n",
    "                if path[i].val > p.val:\n",
    "                    return path[i]\n",
    "        pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        def inorder(root: TreeNode):\n",
    "            if root == None:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            result.append(root.val)\n",
    "            inorder(root.right)\n",
    "        result = []\n",
    "        inorder(root)\n",
    "        for index,num in enumerate(result):\n",
    "            if num == p.val and index + 1 < len(result):\n",
    "                return TreeNode(result[index + 1])\n",
    "        return None        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            res = []\n",
    "            def dfs(root):\n",
    "                if not root: return\n",
    "                dfs(root.left)\n",
    "                res.append(root)\n",
    "                dfs(root.right)\n",
    "            \n",
    "            dfs(root)\n",
    "            n = len(res)\n",
    "            for i in range(n):\n",
    "                if res[i] == p:\n",
    "                    if i == n - 1:\n",
    "                        return \n",
    "                    return res[i + 1]\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    pre = None\n",
    "    ret = None\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        def check(node):\n",
    "            if not node: return\n",
    "            # 中序遍历（左、中、右）\n",
    "            check(node.left)\n",
    "            # 若当前节点的前置节点为p，则说明当前节点即为所求\n",
    "            if self.pre == p: self.ret = node\n",
    "            self.pre = node\n",
    "            check(node.right)\n",
    "        \n",
    "        check(root)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        stack = []\n",
    "        cur = root\n",
    "        pre = None\n",
    "        while cur or len(stack) > 0:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            if pre and pre == p:\n",
    "                return cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        \n",
    "        return None\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        succ = None\n",
    "        if p.right:\n",
    "            succ = p.right\n",
    "            while succ.left:\n",
    "                succ = succ.left\n",
    "            return succ\n",
    "        \n",
    "        node = root\n",
    "        while node:\n",
    "            if p.val < node.val:\n",
    "                succ = node\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        return succ\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:\n",
    "        # 有右子树的情况\n",
    "        if p.right != None:\n",
    "            ans = p.right\n",
    "            while ans.left:\n",
    "                ans = ans.left\n",
    "            return ans\n",
    "\n",
    "        # 没有右子树时，若p为父节点的右节点，\n",
    "        # 弹出，直到找到第一个左节点的父节点\n",
    "        \n",
    "        parents = []\n",
    "        def search(root):\n",
    "            if root is None:\n",
    "                return False\n",
    "            if root == p: # 回溯\n",
    "                return True\n",
    "            parents.append(root)\n",
    "            if search(root.left):\n",
    "                return True\n",
    "            if search(root.right):\n",
    "                return True\n",
    "            parents.pop()\n",
    "            return False\n",
    "        search(root)\n",
    "        \n",
    "        while parents and parents[-1].right == p:\n",
    "            p = parents.pop()\n",
    "\n",
    "        if parents:\n",
    "            return parents[-1]\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            nodes.append(root)\n",
    "            dfs(root.right)\n",
    "\n",
    "        nodes = []\n",
    "        dfs(root)\n",
    "        for i in range(len(nodes) - 1):\n",
    "            if nodes[i].val == p.val:\n",
    "                return nodes[i + 1]\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':\n",
    "        if root is None:\n",
    "            return None\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            if node.left is not None:\n",
    "                dfs(node.left)\n",
    "            nonlocal res\n",
    "            res.append(node)\n",
    "            if node.right is not None:\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        ind_ = res.index(p)\n",
    "        if ind_==len(res)-1:\n",
    "            return None\n",
    "        else:\n",
    "            return res[ind_+1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
